package com.dempsey.voronoiweb.utils;


import com.dempsey.voronoiweb.project.entity.*;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * Package: dao
 * Description：
 * Author: Dempsey
 * Date:  2020/3/7 15:31
 * Modified By:
 */
public class CreateVoronoiMap {

    //绘制维诺图
    public static List<Cover> createVoronoiMap(Point centerPoint,
                                               double radius,
                                               List<DelaunayTriangle> triangles,
                                               List<Edge> broderEdges,
                                               List<Point> broderPoints,
                                               List<Point> points) {
        //基站和它的覆盖区 集合
        List<Cover> cover = new ArrayList<>();
        //遍历求覆盖区
        for (Point point : points) {
            //先完成非边缘点的覆盖区绘制

            //获取点有关的三角形集合
            List<DelaunayTriangle> triangleList = getTrianglesListWithPoint(triangles, point);

            List<Point> siteList = new ArrayList<>();
            //遍历所有三角形
            for (DelaunayTriangle delaunayTriangle : triangleList) {
                // 拿到外接圆圆心
                Point site = delaunayTriangle.getCenterPoint();
                // 如果外接圆圆心在范围外
                if (CreateDelaunayTriangleMap.distanceWithTwoPoints(site, centerPoint) > radius) {
                    // 点集加入 其与其他所有外接圆圆心连成的线段 与 范围 的交点
                    List<Point> otherPointList = triangleList.stream()
                            .filter(t -> !t.equals(delaunayTriangle))
                            .map(DelaunayTriangle::getCenterPoint)
                            .collect(Collectors.toList());
                    for (Point otherPoint : otherPointList) {
                        siteList.add(getCrossPoint(site, otherPoint, centerPoint, radius));
                    }
                } else {
                    // 如果这个点是个边缘点
                    if (broderPoints.contains(point)) {
                        // 求该三角形的边缘边的中垂线与范围的交点
                        for (Edge edge : delaunayTriangle.getEdges()) {
                            if (broderEdges.contains(edge)) {
                                siteList.add(getCrossSites(edge, centerPoint, radius));
                            }
                        }
                    } else {
                        //获取边缘点有关的边缘边集合
                        List<Edge> bEforPoint = CreateDelaunayTriangleMap.getEdgeListWithPoint(broderEdges, point);
                        //求边缘点中垂线与图形边界的交点，合并入覆盖区边缘点集
                        siteList.addAll(getCrossSites2(bEforPoint, centerPoint, radius));
                    }
                    siteList.add(site);
                }
            }

            //最后将结果组合存入cover中
            cover.add(new Cover(point, siteList, getEdgesWithSites(siteList)));
        }


        return cover;
    }

    /*---------------------------我是快乐的分割线----------------------*/

    /**
     * 线段与圆的交点（忽略没有交点的情况）
     *
     * @param p1          the p 1
     * @param p2          the p 2
     * @param centerPoint the center point
     * @param radius      the radius
     * @return the cross point
     */
    public static Point getCrossPoint(Point p1, Point p2, Point centerPoint, double radius) {
        Line line = p1.getLongitude() <= p2.getLongitude() ? new Line(p1, p2) : new Line(p2, p1);
        double k = line.getK();
        double b = line.getB();
        double c = centerPoint.getLongitude();
        double d = centerPoint.getLatitude();
        double aa = k * k + 1;
        double bb = -2 * c - 2 * k * d + 2 * k * b;
        double cc = b * b + c * c + d * d - 2 * b * d - radius * radius;
        double x1 = (-bb + Math.pow(Math.pow(bb, 2) - 4 * aa * cc, 0.5)) / (2 * aa);
        double x2 = (-bb - Math.pow(Math.pow(bb, 2) - 4 * aa * cc, 0.5)) / (2 * aa);
        if (line.getP1().getLongitude() <= x1 && x1 <= line.getP2().getLongitude()) {
            double y1 = k * x1 + b;
            return new Point(x1, y1);
        }
        double y2 = k * x2 + b;
        return new Point(x2, y2);
    }

    //求边缘边与图形边界的交点集
    public static Point getCrossSites(Edge edge, Point centerPoint, double radius) {
        Point p1 = edge.getA();
        Point p2 = edge.getB();
        double x1, x2, x3, y1, y2, y3, k1, k2, b1, b2, xc, yc;
        x1 = p1.getLongitude();
        x2 = p2.getLongitude();
        y1 = p1.getLatitude();
        y2 = p2.getLatitude();
        xc = centerPoint.getLongitude();
        yc = centerPoint.getLatitude();
        //点3是中点，线2是中垂线
        x3 = (x1 + x2) / 2;
        y3 = (y1 + y2) / 2;
        k1 = (y1 - y2) / (x1 - x2);
        b1 = y1 - k1 * x1;
        k2 = -1 / k1;
        b2 = y3 - k2 * x3;
        double a = k2 * k2 + 1;
        double b = 2 * k2 * b2 - 2 * xc - 2 * k2 * yc;
        double c = -(radius * radius - xc * xc - b2 * b2 - yc * yc + 2 * b2 * yc);
        double Cross_x1 = (-b + Math.sqrt(b * b - 4 * a * c)) / (2 * a);
        double Cross_x2 = (-b - Math.sqrt(b * b - 4 * a * c)) / (2 * a);
        if (Math.abs(Cross_x1 - x3) < Math.abs(Cross_x2 - x3)) {
            return new Point(Cross_x1, k2 * Cross_x1 + b2);
        }
        return new Point(Cross_x2, k2 * Cross_x2 + b2);


    }

    //求边缘边与图形边界的交点集
    public static List<Point> getCrossSites2(List<Edge> bEforPoint, Point centerPoint, double radius) {
        List<Point> CrossSites = new ArrayList<>();
        for (Edge edge : bEforPoint) {
            Point p1 = edge.getA();
            Point p2 = edge.getB();
            double x1, x2, x3, y1, y2, y3, k1, k2, b1, b2, xc, yc;
            x1 = p1.getLongitude();
            x2 = p2.getLongitude();
            y1 = p1.getLatitude();
            y2 = p2.getLatitude();
            xc = centerPoint.getLongitude();
            yc = centerPoint.getLatitude();
            //点3是中点，线2是中垂线
            x3 = (x1 + x2) / 2;
            y3 = (y1 + y2) / 2;
            k1 = (y1 - y2) / (x1 - x2);
            b1 = y1 - k1 * x1;
            k2 = -1 / k1;
            b2 = y3 - k2 * x3;
            double a = k2 * k2 + 1;
            double b = 2 * k2 * b2 - 2 * xc - 2 * k2 * yc;
            double c = -(radius * radius - xc * xc - b2 * b2 - yc * yc + 2 * b2 * yc);
            double Cross_x1 = (-b + Math.sqrt(b * b - 4 * a * c)) / (2 * a);
            double Cross_x2 = (-b - Math.sqrt(b * b - 4 * a * c)) / (2 * a);
            if (Math.abs(Cross_x1 - x3) < Math.abs(Cross_x2 - x3)) {
                CrossSites.add(new Point(Cross_x1, k2 * Cross_x1 + b2));
            } else {
                CrossSites.add(new Point(Cross_x2, k2 * Cross_x2 + b2));
            }
        }

        return CrossSites;
    }

    //对点集将他们连接，形成一个区块，内部没有连接
    public static List<Edge> getEdgesWithSites(List<Point> siteList) {
        List<Edge> coverToPoint = new ArrayList<>();
        //先把所有点连起来
        for (Point point : siteList) {
            for (Point point1 : siteList) {
                if (!point.equals(point1)) {
                    coverToPoint.add(new Edge(point, point1));
                }
            }
        }

        //遍历去重
        for (int i = coverToPoint.size() - 1; i >= 1; i--) {
            for (int j = i - 1; j >= 0; j--) {
                if (coverToPoint.get(i).equals(coverToPoint.get(j))) {
                    coverToPoint.remove(j);
                    break;
                }
            }
        }

        //遍历去交线
        Set<Integer> indexs = new HashSet<>();
        List<Integer> integers = new ArrayList<>();
        for (int i = coverToPoint.size() - 1; i >= 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                if (Cross(coverToPoint.get(i), coverToPoint.get(j))) {
                    indexs.add(i);
                    indexs.add(j);
                }
            }
        }
        integers.addAll(indexs);
        integers.sort((o1, o2) -> o2 - o1);
        for (Integer integer : integers) {
            coverToPoint.remove((int) integer);
        }

        return coverToPoint;
    }

    //判断连接，条件：两线段没有同一端点，两线段相交
    public static boolean Cross(Edge e1, Edge e2) {
        if (e1.getA().equals(e2.getA()) || e1.getA().equals(e2.getB()) ||
                e1.getB().equals(e2.getA()) || e1.getB().equals(e2.getB())) {
            return false;
        } else {
            //规范化两线段，两点分别为AB，CD，A在B左边，C在D左边
            //定义x的范围为AC的大，BD的小
            //然后求交点，判断交点的x在不在范围中
            double xA, xB, xC, xD;
            double yA, yB, yC, yD;
            xA = e1.getA().getLongitude();
            xB = e1.getB().getLongitude();
            xC = e2.getA().getLongitude();
            xD = e2.getB().getLongitude();
            yA = e1.getA().getLatitude();
            yB = e1.getB().getLatitude();
            yC = e2.getA().getLatitude();
            yD = e2.getB().getLatitude();
            if (xA > xB) {
                double temp;
                temp = xA;
                xA = xB;
                xB = temp;
                temp = yA;
                yA = yB;
                yB = temp;
            }
            if (xC > xD) {
                double temp;
                temp = xC;
                xC = xD;
                xD = temp;
                temp = yC;
                yC = yD;
                yD = temp;
            }
            //要是两根线差的十万八千里，就不用算下去了
            if (xB < xC || xA > xD) {
                return false;
            } else {
                double k1 = (yB - yA) / (xB - xA);
                double k2 = (yD - yC) / (xD - xC);
                double b1 = yA - k1 * xA;
                double b2 = yC - k2 * xC;
                double x = (b2 - b1) / (k1 - k2);//x是两线交点的横坐标
                if (x > Math.max(xA, xC) && x < Math.min(xB, xD)) {
                    return true;
                }
            }
        }
        return false;
    }

    //得到一个点所有关联的triangles
    public static List<DelaunayTriangle> getTrianglesListWithPoint(List<DelaunayTriangle> triangles, Point point) {
        List<DelaunayTriangle> trianglesListWithPoint = new ArrayList<>();//点有关的三角形集
        for (DelaunayTriangle triangle : triangles) {
            if (triangle.getP1().equals(point) || triangle.getP2().equals(point) || triangle.getP3().equals(point)) {
                trianglesListWithPoint.add(triangle);
            }
        }
        return trianglesListWithPoint;
    }
}
